import java.util.ArrayList;
import java.util.List;

/**
* @description: 894. 所有可能的真二叉树
* @author hewei
* @date 2022/9/16 15:18
* @version 1.0
*/

public class AllPossibleFBT {

    public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> list = new ArrayList<>();
        if (n == 1) {
            list.add(new TreeNode());
            return list;
        }
        int count = n - 2;
        while (count > 0) {
            List<TreeNode> list1 = allPossibleFBT(count);
            List<TreeNode> list2 = allPossibleFBT(n - 1 - count);
            for (TreeNode node1 : list1) {
                for (TreeNode node2 : list2) {
                    TreeNode node = new TreeNode();
                    node.left = node1;
                    node.right = node2;
                    list.add(node);
                }
            }
            count -= 2;
        }
        return list;
    }
}
